package org.dormi.learn.definition;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.*;

/**
 * @author : dormi330
 * @since : 2021/1/27/0027
 * 图的定义
 */
public class Graph {
    private static final Logger log = LoggerFactory.getLogger(Graph.class);

    /** 所有顶点 */
    private final Set<Vertex> vertices = new HashSet<>();

    /** 邻接表 */
    private final List<List<Vertex>> adjList = new ArrayList<>();

    /** 邻接表的map key=顶点 */
    private final Map<Vertex, List<Vertex>> adjMap = new HashMap<>();

    private Vertex entry;

    public Graph() {
    }

    public Vertex addVertex(Vertex v) {
        Vertex origin = null;
        for (Vertex aVertex : vertices) {
            if (aVertex.equals(v)) {
                origin = aVertex;
                break;
            }
        }

        if (origin == null) {
            log.info("addVertex, [{}]", v);
            origin = v;
            vertices.add(origin);
            List<Vertex> oneLine = new ArrayList<>();
            oneLine.add(origin);
            adjList.add(oneLine);
            adjMap.put(origin, oneLine);
        } else {
            log.debug("addVertex, 顶点[{}]已存在", origin);
        }

        return origin;
    }

    /** 添加一条边 */
    public void addEdge(Vertex v1, Vertex v2) {
        Vertex v1Real = addVertex(v1);
        Vertex v2Real = addVertex(v2);
        adjMap.get(v1Real).add(v2Real);
    }

    public void addEdge(List<Edge> edges) {
        for (Edge e : edges) {
            addEdge(e.v1, e.v2);
        }
    }

    /** dfs后, 移除 back edge */
    public void removeBackEdgeAfterDFS() {
        for (List<Vertex> oneLine : adjList) {
            if (oneLine.size() == 1) {
                continue;
            }

            /* 在edge u -> v中, 如果
             * arrive[u]    > arrival[v]
             * departure[u] < departure[v]
             * 则是 back edge
             */
            List<Vertex> toRemove = new ArrayList<>(oneLine.size() - 1);
            Vertex u = oneLine.get(0);
            int arrivalU = u.getArrival();
            int departureU = u.getDeparture();

            for (int i = 1; i < oneLine.size(); i++) {
                Vertex v = oneLine.get(i);
                int arrivalV = v.getArrival();
                int departureV = v.getDeparture();
                // 如果
                if (arrivalU > arrivalV && departureU < departureV) {
                    toRemove.add(v);
                    log.info("remove edge[{} ->{}]", u.uid, v.uid);
                }
            }

            if (!toRemove.isEmpty()) {
                oneLine.removeAll(toRemove);
            }
        }
    }

    @Override
    public String toString() {
        return "Graph{" +
                "vertices=" + vertices +
                ", adjList=" + adjList +
                ", adjMap=" + adjMap +
                ", entry=" + entry +
                '}';
    }

    public Set<Vertex> getVertices() {
        return vertices;
    }

    public void setEntry(Vertex v) {
        Vertex real = addVertex(v);
        this.entry = real;
    }

    public Vertex getEntry() {
        return entry;
    }

    public Map<Vertex, List<Vertex>> getAdjMap() {
        return adjMap;
    }


}
